package sword;

/**
 * @Author: 海琳琦
 * @Date: 2022/6/7 16:03
 * https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 */
public class Title13 {

    int count;

    public int movingCount(int m, int n, int k) {
        int[][] visited = new int[m][n];
        dfs(m, n, 0, 0, k, visited);
        return count;
    }

    private void dfs(int m, int n, int i, int j, int k, int[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] == 1 || getSum(i) + getSum(j) > k) {
            return;
        }
        visited[i][j] = 1;
        count++;
        dfs(m, n, i + 1, j, k, visited);
        dfs(m, n, i, j + 1, k, visited);
    }

    private int getSum(int num) {
        //获得位数和
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }

    public static void main(String[] args) {

    }
}
